//----------------------------------------------------------------------
// File:			pr_queue.h
// Programmer:		Sunil Arya and David Mount
// Description:		Include file for priority queue and related
// 					structures.
// Last modified:	01/04/05 (Version 1.0)
//----------------------------------------------------------------------
// Copyright (c) 1997-2005 University of Maryland and Sunil Arya and
// David Mount.  All Rights Reserved.
//
// This software and related documentation is part of the Approximate
// Nearest Neighbor Library (ANN).  This software is provided under
// the provisions of the Lesser GNU Public License (LGPL).  See the
// file ../ReadMe.txt for further information.
//
// The University of Maryland (U.M.) and the authors make no
// representations about the suitability or fitness of this software for
// any purpose.  It is provided "as is" without express or implied
// warranty.
//----------------------------------------------------------------------
// History:
//	Revision 0.1  03/04/98
//		Initial release
//----------------------------------------------------------------------

#ifndef PR_QUEUE_H
#define PR_QUEUE_H

#include <ANN/ANNx.h>    // all ANN includes
#include <ANN/ANNperf.h> // performance evaluation

//----------------------------------------------------------------------
//	Basic types.
//----------------------------------------------------------------------
typedef void *  PQinfo; // info field is generic pointer
typedef ANNdist PQkey;  // key field is distance

//----------------------------------------------------------------------
//	Priority queue
//		A priority queue is a list of items, along with associated
//		priorities.  The basic operations are insert and extract_minimum.
//
//		The priority queue is maintained using a standard binary heap.
//		(Implementation note: Indexing is performed from [1..max] rather
//		than the C standard of [0..max-1].  This simplifies parent/child
//		computations.)  User information consists of a void pointer,
//		and the user is responsible for casting this quantity into whatever
//		useful form is desired.
//
//		Because the priority queue is so central to the efficiency of
//		query processing, all the code is inline.
//----------------------------------------------------------------------

class ANNpr_queue
{

  struct pq_node
  {              // node in priority queue
    PQkey  key;  // key value
    PQinfo info; // info field
  };
  int       n;        // number of items in queue
  int       max_size; // maximum queue size
  pq_node * pq;       // the priority queue (array of nodes)

public:
  ANNpr_queue(int max) // constructor (given max size)
  {
    n = 0;                     // initially empty
    max_size = max;            // maximum number of items
    pq = new pq_node[max + 1]; // queue is array [1..max] of nodes
  }

  ~ANNpr_queue() // destructor
  {
    delete[] pq;
  }

  ANNbool
  empty() // is queue empty?
  {
    if (n == 0)
      return ANNtrue;
    else
      return ANNfalse;
  }

  ANNbool
  non_empty() // is queue nonempty?
  {
    if (n == 0)
      return ANNfalse;
    else
      return ANNtrue;
  }

  void
  reset() // make existing queue empty
  {
    n = 0;
  }

  inline void
  insert(       // insert item (inlined for speed)
    PQkey  kv,  // key value
    PQinfo inf) // item info
  {
    if (++n > max_size)
      annError("Priority queue overflow.", ANNabort);
    int r = n;
    while (r > 1)
    { // sift up new item
      int p = r / 2;
      ANN_FLOP(1)          // increment floating ops
      if (pq[p].key <= kv) // in proper order
        break;
      pq[r] = pq[p]; // else swap with parent
      r = p;
    }
    pq[r].key = kv; // insert new item at final location
    pq[r].info = inf;
  }

  inline void
  extr_min(       // extract minimum (inlined for speed)
    PQkey &  kv,  // key (returned)
    PQinfo & inf) // item info (returned)
  {
    kv = pq[1].key;         // key of min item
    inf = pq[1].info;       // information of min item
    PQkey kn = pq[n--].key; // last item in queue
    int   p = 1;            // p points to item out of position
    int   r = p << 1;       // left child of p
    while (r <= n)
    {             // while r is still within the heap
      ANN_FLOP(2) // increment floating ops
                  // set r to smaller child of p
      if (r < n && pq[r].key > pq[r + 1].key)
        r++;
      if (kn <= pq[r].key) // in proper order
        break;
      pq[p] = pq[r]; // else swap with child
      p = r;         // advance pointers
      r = p << 1;
    }
    pq[p] = pq[n + 1]; // insert last item in proper place
  }
};

#endif
